package mid.class4;

/**
 * 并查集
 * {a}、{b}、{c}、{d}、{e}、{f}
 * <p>
 * 核心方法：
 * int find(x):查找节点 x 所属的集合
 * boolean isSameSet(x,y):判断 x 和 y 是否属于同一个集合
 * void union(x,y): 合并两个集合,使用按秩合并的策略，即将秩较小的树合并到秩较大的树下，从而保持树的平衡，避免树的高度过大。
 * <p>
 * 1.网上找到代表元素
 * 2.小的头挂大的头
 * 3.扁平化
 */
public class Code01_UnionFind {

    private static class UnionFind {
        public static int MAX = 1000001;

        public static int[] father = new int[MAX];

        public static int[] size = new int[MAX];

        public static int[] stack = new int[MAX];

        public static int n;

        public static void build() {
            for (int i = 0; i < n; i++) {
                father[i] = i;
                size[i] = 1;
            }
        }

        // i 号节点，往上一直找，找到代表节点后返回
        public int find(int i) {
            int size = 0;
            while (i != father[i]) { // 判断是否指向本身
                stack[size++] = i;
                i = father[i];
            }
            // 沿途节点收集完毕，i已经跳到代表节点
            while (size > 0) {
                father[stack[--size]] = i;
            }
            return i;
        }

        public boolean isSameSet(int x, int y) {
            return find(x) == find(y);
        }

        public void union(int x, int y) {
            int fx = find(x);
            int fy = find(y);
            if (fx != fy) {
                if (size[fx] >= size[fy]) {
                    size[fx] += size[fy];
                    father[fy] = fx;
                } else {
                    size[fy] += size[fx];
                    father[fx] = fy;
                }
            }
        }
    }
}


